Reed-Solomon (RS) codes are prevalent in many communication systems and data storage devices. They are powerful codes that can be efficiently decoded using traditional algebraic hard-decision decoding (HDD) methods such as the Berlekamp-Massey algorithm (denoted by BM-HDDA) and Euclid's algorithm. However, these traditional methods fail to exploit soft reliability information readily available at the output of the detector. With moderate complexity, but also with little improvement in performance for practical values of signal-to-noise ratio (SNR), generalized minimum distance (GMD) decoding, Chase decoding, and their variations were devised to make use of soft reliability information. Reliability-based decoding can also be applied to the binary images of RS codes. Based on the list decoding algorithm of Guruswami and Sudan, Koetter and Vardy (KV) proposed an algebraic soft-decision (ASD) decoding method for RS codes that incorporates reliability to improve performance over previous algebraic decoding algorithms. Analysis, extensions, modifications, refinements, and variations of KV algorithm are numerous in the art.
To improve performance beyond the ASD algorithms, non-algebraic methods have been proposed by Vardy and Be'ery to achieve the maximum-likelihood decoding (MLD) performance based on binary representation of an RS code as a union of cosets. However, the running time of these decoding methods grows exponentially with the length of the code. Indeed, it has been shown by Guruswami and Vardy that MLD of RS codes is NP-hard. Except for codes of lengths up to 15, decoding based on the trellis representation of RS codes is not feasible due to the enormous number of states in the trellis. Liu and Lin devised a turbo algorithm for soft-decision decoding (SDD) of RS codes based on decomposing the binary image of an RS code into binary component codes with relatively small trellis complexities, which are concatenated in a way that permits turbo decoding of RS codes of lengths up to 127.
Iterative decoding methods based on belief propagation (BP), such as the sum-product algorithm (SPA) and the min-sum algorithm (MSA), were proposed to decode low-density parity-check (LDPC) codes resulting in excellent performance with reasonable complexity that allows these codes to be used in practical applications. These decoding algorithms work on the parity-check matrices of LDPC codes which are sparse and their associated Tanner graphs have small number of short cycles, if any. However, due to the high-density of nonzero elements in their parity-check matrices and large number of short cycles, especially cycles of length four, in their associated Tanner graphs, direct application of these decoding methods is not suitable for RS codes. To overcome these difficulties, Jiang and Narayanan (JN) proposed an iterative BP-algorithm for decoding RS codes that uses a binary parity-check matrix for the code that is adapted using Gaussian elimination before each decoding iteration, in order to make the variable nodes (VNs) of lowest reliability connected with single edges to check nodes (CNs). Since this algorithm adapts parity-check matrices before running a decoding iteration based on BP, it is commonly referred to as an adaptive-BP-algorithm (or simply ABPA). Although the JN-ABPA gives good performance, its complexity may not be tolerable in practical applications. To reduce the complexity, it was proposed to use a redundant fixed set of parity-check equations corresponding to low-weight codewords in the binary image of the dual code, and select a subset of these equations based on the least reliable bits for decoding. For further improvement in performance, El-Khamy and McEliece (KM) presented an algorithm that combines the KV-ASD and the JN-ABPA. However, this improved ABPA, called KM-ABP-ASD algorithm (or simply KM-ABP-ASDA), still requires a very large computational complexity for practical applications. There is a need in the art for systems and methods for efficiently encoding and/or decoding information bits with reduced complexity.